Expression Add Operators

Given a string that contains only digits 0-9 and a target value, return all possibilities to add binary operators (not unary) +, -, or * between the digits so they evaluate to the target value.

Examples: 

  1. "123", 6 -> ["1+2+3", "1*2*3"] 
  2. "232", 8 -> ["2*3+2", "2+3*2"]
  3. "105", 5 -> ["1*0+5","10-5"]
  4. "00", 0 -> ["0+0", "0-0", "0*0"]
  5. "3456237490", 9191 -> []

Solution:

  1. public class Solution {
  2.   public List<String> addOperators(String num, int target) {
  3.     List<String> res = new ArrayList<>();
  5.     if (num == null || num.length() == 0) 
  6.       return res;
  8.     helper(num, target, 0, 0, 0, "", res);
  10.     return res;
  11.   }
  13.   public void helper(String num, int target, int index, long total, long last, String sol, List<String> res){
  14.     if (index == num.length()) {
  15.       if (target == total)
  16.         res.add(sol);
  18.       return;
  19.     }
  21.     for (int i = index; i < num.length(); i++) {
  22.       // for example, input is "105", we don't need answer like "1*05"
  23.       if (i > index && num.charAt(index) == '0') 
  24.         break;
  26.       long curr = Long.parseLong(num.substring(index, i + 1));
  28.       if (index == 0) {
  29.         // 第一个数
  30.         helper(num, target, i + 1, curr, curr, sol + curr, res);
  31.       } else {
  32.         // 不是第一个数, 我们可以添加运算符了
  33.         helper(num, target, i + 1, total + curr,  curr, sol + "+" + curr, res);
  34.         helper(num, target, i + 1, total - curr, -curr, sol + "-" + curr, res);
  35.         helper(num, target, i + 1, total - last + last * curr, last * curr, sol + "*" + curr, res);
  36.       }
  37.     }
  38.   }
  39. }